
import heapq
class MedianFinder:
    
    def __init__(self):
        self.maxh_low=[]
        self.minh_high=[]
    def addNum(self,num):
        if len(self.maxh_low)==0 or num<=-self.maxh_low[0]:
            heapq.heappush(self.maxh_low,-num)
            if len(self.maxh_low)>len(self.minh_high)+1:
                heapq.heappush(self.minh_high,-heapq.heappop(self.maxh_low))
        else:
            heapq.heappush(self.minh_high,num)
            if len(self.maxh_low)<len(self.minh_high):
                heapq.heappush(self.maxh_low,-heapq.heappop(self.minh_high))

    def findMedian(self):
        if (len(self.minh_high)+len(self.maxh_low))%2==1:
            return -self.maxh_low[0]
        else: return (-self.maxh_low[0]+self.minh_high[0])/2

def solve(lst1,lst2):
    mf=MedianFinder()
    ans=[None]
    for i in range(1,len(lst1)):
        if lst1[i]=='addNum':
            ans.append(None)
            mf.addNum(lst2[i][0])
        else:
            ans.append(mf.findMedian())
    return ans 

lst1=["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
lst2=[[], [1], [2], [], [3], []]
print(solve(lst1,lst2))

            


